#include "Tree.h"
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
BTNode* BinaryTreeCreate(BTDataType* arr,int n,int* pi)
{
	if (arr == NULL)
		return NULL;
	//if (*pi >= n)
	//	return NULL;
	if (arr[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyNode(arr[*pi]);
	(*pi)++;
	root->left = BinaryTreeCreate(arr,n,pi);
	root->right = BinaryTreeCreate(arr,n, pi);
	return root;
}
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
}


void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PreOrder(root->left);
	printf("%c ", root->val);
	PreOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PreOrder(root->left);
	PreOrder(root->right);
	printf("%c ", root->val);

}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLeafKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if ((root->left == NULL && root->right == 0)&&k==1)
		return 1;
	if (k==0)
	{
		return 0;
	}
	return BinaryTreeLeafKSize(root->left, k - 1) + BinaryTreeLeafKSize(root->right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
		return root;
	BTNode* ret1 = BinaryTreeFind(root->left,x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->right,x);
	if (ret2)
		return ret2;
	return NULL;
}

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int height1 = BinaryTreeHeight(root->left);
	int height2 = BinaryTreeHeight(root->right);
	return height1 > height2 ? height1 + 1 : height2 + 1;
}


bool BinaryTreeComplete1(BTNode* root, Stack* pst1, Stack* pst2)
{
	StackPush(pst2, root);
	while ((!StackEmpty(pst1)) || (!StackEmpty(pst2)))
	{
		if (StackEmpty(pst1))
		{
			while (!StackEmpty(pst2))
			{
				BTNode* move = StackTop(pst2);
				StackPop(pst2);
				StackPush(pst1, move);
			}
		}
		root = StackTop(pst1);
		StackPop(pst1);
		if (root == NULL)
		{
			break;
		}

		StackPush(pst2, root->left);
		StackPush(pst2, root->right);
	}
	while ((!StackEmpty(pst1)) || (!StackEmpty(pst2)))
	{
		if (StackEmpty(pst1))
		{
			while (!StackEmpty(pst2))
			{
				BTNode* move = StackTop(pst2);
				StackPop(pst2);
				StackPush(pst1, move);
			}
		}
		root = StackTop(pst1);
		StackPop(pst1);
		if (root != NULL)
		{
			return false;
		}
	}
	return true;
}
bool BinaryTreeComplete(BTNode* root)
{
	Stack st1;
	Stack st2;
	StackInit(&st1);
	StackInit(&st2);
	bool ret = BinaryTreeComplete1(root, &st1, &st2);
	StackDestroy(&st1);
	StackDestroy(&st2);
	return ret;
}
void LevelOrder1( BTNode* root, Stack* pst1,Stack* pst2)
{
	StackPush(pst2, root);
	while ((!StackEmpty(pst1))||(!StackEmpty(pst2)))
	{
		if (StackEmpty(pst1))
		{
			while (!StackEmpty(pst2))
			{
				BTNode* move = StackTop(pst2);
				StackPop(pst2);
				StackPush(pst1, move);
			}
		}
		root = StackTop(pst1);
		StackPop(pst1);
		printf("%c ", root->val);
		if (root->left)
		{
			StackPush(pst2, root->left);
		}
		if (root->right)
		{
			StackPush(pst2, root->right);
		}
	}
}
void LevelOrder(BTNode* root)
{
	Stack st1;
	Stack st2;
	StackInit(&st1);
	StackInit(&st2);
	LevelOrder1(root,&st1,&st2);
	StackDestroy(&st1);
	StackDestroy(&st2);
}

